home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / UnionFind.cpp < prev    next >
C/C++ Source or Header  |  1999-07-13  |  2KB  |  126 lines
  1. #include "UnionFind.h"
  2.  
  3. #include "XLongList.h"
  4.  
  5.  
  6. UnionFind::UnionFind() {
  7.     mDimSize = 0;
  8.     mElements = NULL;
  9. }
  10.  
  11. UnionFind::~UnionFind() {
  12.     if ( mElements )
  13.         delete mElements;
  14. }
  15.  
  16.  
  17. long UnionFind::Find( long inA ) {
  18.     long i, newSize, next;
  19.     unsigned short* newmem;
  20.  
  21.     // Expand our list of elements if we need to...        
  22.     if ( inA >= mDimSize ) {
  23.  
  24.         newSize = inA + 20;
  25.         newmem = new unsigned short[ newSize + 1 ];
  26.         for ( i = 0; i < mDimSize; i++ )
  27.             newmem[ i ] = mElements[ i ];
  28.         delete mElements;
  29.         for ( i = mDimSize; i < newSize; i++ )
  30.             newmem[ i ] = i;
  31.         mDimSize = newSize;
  32.         mElements = newmem;
  33.     }
  34.  
  35.  
  36.  
  37.     // Find w/ path compression
  38.     while ( mElements[ inA ] != inA ) {
  39.         next = mElements[ inA ];
  40.         if ( mElements[ next ] == next )
  41.             return next;
  42.         else {
  43.             inA = mElements[ inA ] = mElements[ next ];
  44.         }
  45.     }
  46.     
  47.     
  48.     return inA;
  49. }
  50.  
  51.  
  52. long UnionFind::LargestSet( long* outSize ) {
  53.     unsigned short* tally = new unsigned short[ mDimSize ];
  54.     long max, set, i;
  55.     
  56.     
  57.     for ( i = 0; i < mDimSize; i++ )
  58.         tally[ i ] = 0;
  59.         
  60.     for ( i = 0; i < mDimSize; i++ )
  61.         tally[ Find( i ) ]++;
  62.         
  63.     max = 0;
  64.     set = 0;
  65.     for ( i = 0; i < mDimSize; i++ ) {
  66.         if ( tally[ i ] > max ) {
  67.             max = tally[ i ];
  68.             set = i;
  69.         }
  70.     }
  71.     
  72.     delete []tally;
  73.     
  74.     if ( outSize )
  75.         *outSize = max;
  76.         
  77.     return set;
  78. }
  79.  
  80.  
  81. void UnionFind::EnumerateSet( long inSetID, XLongList& outSet ) {
  82.     long i;
  83.     
  84.     outSet.RemoveAll();
  85.     for ( i = 0; i < mDimSize; i++ ) {
  86.         if ( Find( i ) == inSetID )
  87.             outSet.Add( i );
  88.     }
  89. }
  90.  
  91.  
  92. void UnionFind::Union( long inA, long inB ) {
  93.     
  94.     // Do the union
  95.     mElements[ Find( inB ) ] = Find( inA );
  96. }
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103. long UnionFind::NumSets() {
  104.     long i, numSets = 0;
  105.     
  106.     for ( i = 0; i < mDimSize; i++ ) {
  107.         if ( mElements[ i ] == i )
  108.             numSets++;
  109.     }
  110.     
  111.     return numSets;
  112. }
  113.  
  114.  
  115.  
  116. void UnionFind::GetSets( XLongList& outSets ) {
  117.     long i;
  118.     
  119.     outSets.RemoveAll();
  120.     for ( i = 0; i < mDimSize; i++ ) {
  121.         if ( mElements[ i ] == i )
  122.             outSets.Add( i );
  123.     }
  124. }
  125.  
  126.